package cn.com.yang.datastruct.shortpath;

import cn.com.yang.datastruct.wgraph.PriorityQueue;
import cn.com.yang.datastruct.wgraph.Vertex;

/**
 * 图最短路径（S集合 U集合） TODO
 * 
 * @author yangyijin
 * @since 2024年2月8日-上午11:09:57
 */
public class Graph {
	// 图的订单和边，边是二维矩阵或者邻接表
	private Vertex[] vertexs;
	private int[][] adjMatix;
	private int nVertex;// 计数器，定点的个数
	private final int MAX_VERTEX = 20;// 最大的顶点个数
	private int nTree;// 计数器，分析集合中S，ntree计数S中的节点个数
	private final int INF = 1000000;// 初始化很大的数
	private DisPar[] upath;// 相当于分析中的U集合
	private int currVertex;// 当前顶点的下标
	private int startToCurrnt = 0;
	public Graph() {
		vertexs = new Vertex[MAX_VERTEX];
		adjMatix = new int[MAX_VERTEX][MAX_VERTEX];
		for (int i = 0; i < MAX_VERTEX; i++) {
			for (int j = 0; j < MAX_VERTEX; j++) {
				adjMatix[i][j] = INF;
			}
		}
		nTree = 0;
		nVertex = 0;
		upath = new DisPar[MAX_VERTEX];
	}

	// 向顶点插入数据
	public void insert(char label) {
		vertexs[nVertex++] = new Vertex(label);
	}

	// 有了顶点够，更新矩阵关系
	public void addEdge(int start, int end, int price) {
		// 有向图
		adjMatix[start][end] = price;
	}

	// 打印指定顶点中的label
	public void displayVertex(int v) {
		System.out.print(vertexs[v].label);
	}
	//最重要的核心部分，实现最短路径的算法
	public void path() {
		//1.选一个节点，起始节点，下标为0的节点做起始节点
		int startNode =0;
		//2.初始化，相当于把该节点放到分析中的S集合
		vertexs[startNode].inInTree = true;
		nTree++;
		//3.初始化，相当于分析中的U集合，以0为起点的路径和距离放入到U集合
		int temps;
		for(int i=0;i<nVertex;i++) {
			temps = adjMatix[startNode][i];
			upath[i] =	new DisPar(temps, startNode);
		}
		//4、5步骤
		int indexMin,tempDis;
		while(nTree<nVertex) {//ntree < nVerts -1
			//从U集合中找最短路径的点，upath中的distance最小的元素
			indexMin = getMin();//找upath数组中值最小的下标
			tempDis = upath[indexMin].distance;//最小距离
			//
			if(tempDis==INF) {
				//说明是孤点
				System.out.println("说明其实点是一个孤点，没有任何邻接点");
				break;
			}else {
				currVertex = indexMin;
				startNode = upath[indexMin].distance;
			}
			//4.把找到的点放到矩阵,分析中的S集合
			vertexs[currVertex].inInTree = true;
			nTree++;
			//5.更新U集合的路径
			adjustUpath();//更新
		}
		//6.循环结束，得到结果
		display();
		//7.还原ntree标记
		nTree=0;
		for(int i=0;i<nVertex;i++) {
			vertexs[i].inInTree=false;
		}
	}

	/**
	 * 展示
	 */
	private void display() {
		for(int j=0;j<nVertex;j++) {
			//到目标节点
			System.out.print(vertexs[j].label+" = ");
			//其实点到目标点的距离
			if(upath[j].distance==INF) {
				System.out.print("∞");
			}else {
				System.out.print(upath[j].distance+" ");
			}
			//拿到父节点
			char parent = vertexs[upath[j].parentVert].label;
			System.out.print("("+parent+")");
		}
		System.out.print("");
	}

	/**
	 * 更新U集合路径
	 * if('B'->'D'\'C'\'E' + 'A'->'B' <'A'->'D'\'C'\'E')就更新U的数据
	 */
	private void adjustUpath() {
		int j=1;//从1开始，跳过起始点0
		while(j<nVertex) {
			//如果扫描到的点，如果在S集合，跳过
			if(vertexs[j].inInTree) {
				j++;
				continue;
			}
			//上面的if过滤后，都是U结合中的点
			//拿到三个距离
			//1.当前节点到上个节点的距离
			int currToj = adjMatix[currVertex][j];
			//2.判断式子中的左边的距离
			int startToj = startToCurrnt + currToj;
			//3.右边的距离
			int rightPath = upath[j].distance;
			if(startToj < rightPath) {
				//更新对应数据
				upath[j].parentVert = currVertex;
				upath[j].distance = startToj;
			}
			j++;
		}
	}

	/**
	 * 找upath数组中值最小的下标
	 * @return
	 */
	private int getMin() {
		int minDest = INF;
		int indexMin = 0;
		for(int i=0;i<nVertex;i++) {
			if(vertexs[i].inInTree && upath[i].distance < minDest) {
				minDest = upath[i].distance;
				indexMin = i;
			}
		}
		return indexMin;
	}
}
